package com.leetcode.studyplan.algorithm.basis;

public class L_844_BackspaceStringCompare {

    public static void main(String[] args) {

        L_844_BackspaceStringCompare compare = new L_844_BackspaceStringCompare();
        String s = "ab#c";
        String t = "ad#c";
        boolean result = compare.backspaceCompare(s, t);
        System.out.println(result);
    }

    public boolean backspaceCompare(String s, String t) {

        int i = s.length() - 1;
        int j = t.length() - 1;

        int skipC = 0;
        int skipD = 0;

        while(i >= 0 || j >= 0) { // 也就是直到所有最后一个字符删除
            // 从字符串尾部开始进行字符对比，先把#号前面定的字符串删除掉
            while (i >= 0) {
                char sC = s.charAt(i);
                if (sC == '#') {
                    skipC++;
                    i--;
                } else if (skipC > 0) {
                    skipC--;
                    i--;
                } else {
                    break;
                }
            }

            while (j >= 0) {
                char sD = t.charAt(j);
                if (sD == '#') {
                    skipD++;
                    j--;
                } else if (skipD > 0){
                    skipD--;
                    j--;
                } else {
                    break;
                }
            }

            if (i >= 0 && j >= 0) {
                if (s.charAt(i) !=  t.charAt(j)) {
                    return false;
                }
            } else {
                // 一个字符串已经遍历结束，而另一字符串的结尾不以‘#’结束，而此时两个字符串肯定不等
                if (i >= 0 || j >= 0) {
                    return false;
                }
                // 若i和j同时小于0，则说明两个比较的字符串已经遍历完成，两个字符串相等。最后会结束循环，返回true
            }
            i--;
            j--;
        }

        return true;
    }

}
